class Solution121 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        vector<int> dp(n);
        int maxnum = prices[n - 1];
        dp[n - 1] = maxnum;
        for (int i = n - 2; i >= 0; i--)
        {
            if (maxnum > prices[i])
            {
                dp[i] = maxnum;
            }
            else
            {
                dp[i] = prices[i];
                maxnum = prices[i];
            }
        }

        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            ret = max(ret, (int)dp[i] - prices[i]);
        }
        return ret;
    }
};


class Solution122 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = 0;    //零代表持有现金
        dp[0][1] = -prices[0];    //1代表持有股票
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);   //上一个必须是持有现金或者持有股票
        }
        return dp[n - 1][0];
    }
};


class Solution123 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(3)));
        dp[0][0][2] = 0;
        dp[0][0][1] = 0;
        dp[0][0][0] = 0;
        dp[0][1][2] = -prices[0];
        dp[0][1][1] = -prices[0];
        dp[0][1][0] = -prices[0];

        for (int i = 1; i < n; i++)
        {
            dp[i][0][2] = dp[i - 1][0][2];
            dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][1][2] + prices[i]);
            dp[i][0][0] = max(dp[i - 1][0][0], dp[i - 1][1][1] + prices[i]);
            dp[i][1][2] = max(dp[i - 1][1][2], dp[i - 1][0][2] - prices[i]);
            dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][1] - prices[i]);
            dp[i][1][0] = dp[i - 1][1][0];
        }

        return dp[n - 1][0][0];
    }
};